Digital Subscriber Lines are the most important means for delivering high-speed Internet access. Crosstalk has been identified as one of the main sources of performance degradation in DSL networks. Crosstalk is the effect of electromagnetic coupling of different lines transmitting in the same binder—the phenomenon can be interpreted as if the signal of one line leaks into all neighboring lines as illustrated in FIG. 1. Balancing crosstalk is a compensating game: decreasing crosstalk by reducing transmit power and thus increasing system performance goes typically along with decreasing individual line performance. Crosstalk is a major impairment for improvements in rate and reach in the network, thus crosstalk is one of the most important limiting factor for better service provisioning and increase in the number of users served by the technology.
Recently, new strategies for dealing with crosstalk have been created. Crosstalk interference in a given receiver of interest depends basically on two factors: the transmitter Power Spectral Densities (PSDs) of all users different than the user of interest and the coupling function from these transmitters to the receiver of interest. There is no possible way to manipulate crosstalk gains in a binder, but it is feasible to design users' PSDs such that crosstalk is minimized by still maintaining the system's data rates, and maybe even increasing it. Strategies to optimize and custom design the users' PSDs are referred to as Dynamic Spectrum Management (DSM).
There are two main approaches for the DSM problem in the DSL: the Rate Maximization Problem (RMP), often also referred to as Rate Adaptive (RA) problem [Starr, Sorbara, Cioffi, Silverman, “DSL Advances”, Prentice Hall] and the Power Minimization Problem (PMP), often also referred to as Fixed Margin (FM) problem [Starr, Sorbara, Cioffi, Silverman, “DSL Advances”, Prentice Hall].
Consider an N-user multicarrier system that splits the available spectra in K tones. Let pnk be the PSD of user n on tone k. Consider the matrix arrangement P(NxK) of all pnk, as follows
                              P                      (                          N              ×              K                        )                          =                              [                                                                                p                    1                    1                                                                    …                                                                      p                    1                    K                                                                                                ⋮                                                  ⋱                                                  ⋮                                                                                                  p                    N                    1                                                                    …                                                                      p                    n                    k                                                                        ]                    .                                    (        0        )            
The upper left-corner element will denote the PSD of user 1 in the first tone. The lower right-corner element will denote the PSD of the N-th line in tone K. One row of matrix P, which will be referred to as Pn, will represent the PSD distribution of user n across all tones, i.e., Pn=[pn1, pn2, . . . , pnK−1, pnK]. One column of matrix P, which will be represented as Pk, will represent the PSD allocation of all users across one tone, i.e., Pk=[p1k, p2k, . . . pN-1k, pNk].
One can formulate the RMP as the task of finding a given matrix P such that the data rate of one given user (say, user 1) is maximized while all other users in the network achieve a minimum desired rate Rnmin and a limited power budget for each user is respected. One but not exclusive formulation of the RMP could be
                    P        =                  arg          ⁢                                          ⁢                                    max              P                        ⁢                          R              1                                                          (        1        )                            such that Rn≧Rnmin∀n>1; Pntot≦Pnmax∀nin which the rates Rnmin denotes the said minimum rate and Pnmax denotes the said maximum power constraints. Pntot can be determined as sum of the n-th row in equation (0) and Rn can be determined as sum of the rate on each tone of user n in the multicarrier system.        
As stated above, the main objective behind the RMP is the optimisation of PSDs under the given set of constraints.
The objective-function of the RMP problem can be re-written as a weighted rate-sum maximization,
                    P        =                              arg            ⁢                                                  ⁢                                          max                P                            ⁢                              ∑                                                      w                    n                                    ⁢                                      R                    n                                    ⁢                                                                          ⁢                  such                  ⁢                                                                          ⁢                  that                  ⁢                                                                          ⁢                                      P                    n                    tot                                                                                ≤                                    P              n              max                        ⁢                          ∀              n                                                          (        2        )            with a certain set of weights or priorities wn of user n. By controlling the wn, one controls how much resources (in terms of power) a line can or must use to achieve a maximum objective. In the solution the set of wn is uniquely determined by the minimum rates constraints and thus no constraints are neglected. Often it is further assumed that
            ∑      n        ⁢          w      n        =      constant    =          C      .      In practice, the right wn are not known in advance and are (iteratively) found such that all rate constraints are respected. In this case, these variables can be interpreted as the amount of channel resources needed for each user to achieve (at least) a specific minimum rate. Often the first user should take “the maximum rest”, i.e.
                              w          1                =                  C          -                                    ∑              2              N                        ⁢                                          w                n                            .                                                          (                  2          ⁢                                          ⁢          a                )            
The interpretation of the w's is further developed, if set C=1, in which case the w's get a proportional meaning.
The PMP can be formulated as the task of finding a set of PSDs for all users as to minimize total power allocated in the network such that a given set of minimum data-rates is achieved. Hence, the PMP problem can be (non-exclusively) described as
                    P        =                  arg          ⁢                                          ⁢                                    max              P                        ⁢                          ∑                                                w                  n                                ⁢                                  P                  n                  tot                                                                                        (                  2          ⁢                                          ⁢          b                )                            such that Rn≧Rnmin; Pntot≦Pnmax∀nin which the wn has the same interpretation of weight or priority as in the case of the RMP (see also Eq. (2)).        
Four properties of the different ways to solve the RMP and the PMP are of higher interest, i.e. complexity, centralization, performance and required knowledge. Whereas complexity can simply be described as number of required operations, performance is usually described as a function of the achieved Rn. Since the achievable rates are related, it is standard procedure to look for the extending of the rate region: the wider, the better. Centralisation refers to the coordination between the determinations of the PSDs for each user. In a non-centralized schemes (usually called autonomous) the PSDs are determined without any further knowledge of other lines (for example their PSDs or channel information). In contrast, in a full-centralized schemes, the knowledge about all users operations and channels are assumed and exploited. In this case a central management is often assumed to concentrate this knowledge and all operations. Required knowledge is the amount of information necessary or assumed in the different schemes to work. Complexity and performance could be considered as a matter of “taste”, centralization and required knowledge are of immediate importance. Channel measurements are time consuming and expensive and centralization is a key question with respect to unbundling of lines and competition between different service providers.
A brief description of existing algorithm follows in chronological order.
The most representative example of a fully autonomous solution to the DSM problem is the Iterative water filling (IWF) method disclosed in W. Yu, G. Ginis, and J. Cioffi, “Distributed multiuser power control for digital subscriber lines,” IEEE Journal on Selected Areas of Communications, vol. 20, pp. 1105-1115, 2002. IWF uses the well-known water-filling solution iteratively across the network with each user utilizing the minimum power necessary to achieve a given minimum data-rate. It enjoys low complexity, autonomous implementation and requires no crosstalk channel knowledge, However, it is clearly sub-optimal in near-far scenarios.
OSB (Optimal Spectum Balancing) demands a fully centralized system in a central agent with complete channel knowledge. Its complexity scales exponentially in the number of user, thus making its use for large networks prohibitive. It assumes convexity of the rate region and use Lagrange variables to decouple the problem across frequency to solve a per-tone maximization to come up with optimal results for the DSM problem. OSB is described in EP 01492261. ISB (Iterative Spectrum Balancing) is the iterative version of OSB. It optimally solves the RMP with smaller computational demands but still requires centralized operation and full channel knowledge.
SCALE disclosed in J. Papandrlopoulos and J. S. Evans, “Low-complexity distributed algorithms for spectrum balancing in multi-user DSL networks,” in IEEE International Conference on Communications (ICC), 2006 utilizes a convex approximation of the original non-convex objective function and iterates through it until this approximation is as close as possible to the original formulation.
ASB described in J. Huang, R. Cenchillon, M. Chiang, M. Moonen, “Autonomous Spectrum Balancing (ASB) for Frequency Selective Interference Channels,” in IEEE International Symposium Infounation Theory (ISIT), Seattle, 2006 uses the concept of a reference line to represent in each modem its impact on other modems. The reference line should represent the typical victim in a binder. In this context a victim of a line A is considered the line, which has most performance degradation due to the crosstalk of this line A. The reference line is used as an opponent line in a two-line optimization scheme performed for each line separately and is classified by its PSD, the crosstalk gain assumed from user n to the reference line and a background noise. ASB is further characterized by the definition of a static, pre-definition (i.e. before the optimization is done) reference line, which is used unchanged and being the same for all lines to be optimized.
Based on that, the following drawbacks follow:                The ASB method demands that each modem must know the reference line parameters before all—in other words, the network needs an initial configuration.        The definition of the reference line is static and does not take into account the dynamic nature of a network, i.e. system changes such as new line or lines going out of the system are not covered.        The utilization and performance of the reference line method is based on the assumption of its most advantageous definition. It is usually unknown in advance what this definition should really be.        Rather complete channel knowledge is necessary to even start further consideration of how a “typical” victim could look like. In reality, this channel knowledge can, in some situations, be imprecise or not available at all.        A reference line is not individually defined for each physical line, i.e. it is defined the same for all lines. This must at least prevent optimality and is probably impossible for large networks due to the spread of relations and channel and system properties.        
Due to the fact that there is only one reference line definition and that this must be defined in advance, any change of the system affects all lines at the same time by a re-initialization of the reference line.